public class InsertSearch {
    public static void main(String[] args) {
        int[] array = new int[100];
        for(int i = 0; i < array.length; i++){
            array[i] = i + 1;
        }

        int res = insertSearch(array,0,array.length - 1,55);
        System.out.println(res);
    }

    /**
     * 插值查找法，这里只能查找有序数组
     * @param array:待查找的数组
     * @param left:左侧索引
     * @param right:右侧索引
     * @param findValue:待查找的值
     * @return：查找元素所在数组中的位置
     */
    public static int insertSearch(int[] array, int left, int right, int findValue){
        //插值查找的公式：mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left])
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);
        int midValue = array[mid];

        if(findValue < midValue){
            return insertSearch(array,left,mid-1,findValue);
        }else if(findValue > midValue){
            return insertSearch(array,mid + 1, right, findValue);
        }else{
            return mid;
        }
    }
}
